import hashlib
import random
import numpy as np
from sympy import symbols, Poly
from ecdsa import SECP256k1, util # 使用 SECP256k1 椭圆曲线进行 Schnorr 签名
from ecdsa.util import string_to_number
from collections import defaultdict

'''
这个版本的重点：
找出签名验证失败的原因 ；p = SECP256k1.order
补充一致性协议部分
'''

# Parameters
# b 的最大值为 b = n − 2t
# n ≥ 3t + 2a − 1
t = 2  # 最大可容忍的恶意节点数
a = 3  # 每个多项式打包的随机值数
n = 3 * t + 2 * a - 1 # 总参与方数目 11
d = t + a - 1  # 长期秘钥多项式的阶数
d_prime = t + 2 * a - 2  # 临时随机值多项式的阶数
curve = SECP256k1.curve  # 获取曲线对象
p = SECP256k1.order # 素数域 p
G = SECP256k1.generator  # 生成元 G (点对象)
SECP256k1_n = SECP256k1.order  # 生成元的阶 n

sigma_shares = []  # 每个参与方持有的共享份额 σ_i = F(i)
public_keys=[]     # 每个参与方持有的公钥份额 S_i = σ_i * G

all_polynomials_h = []
all_polynomials_z = []
all_polynomials_y = []

commitments = []  # 存储承诺值的列表，n个参与者，每人生成t+2*a-1个承诺
encrypted_shares = []  # 存储所有加密后的 ρij = Hi(j)
decrypted_shares = []  # 存储所有解密后的 ρij = Hi(j)
Hu_list = []  # 存储所有 Hu(x)

ru_dict = {}  # 存储 ru,v
Ru_dict = {}  # 存储 Ru,v
rhoju_dict = {}  # 存储 ρju，key 为 (j, u)
deltauv_dict = {}
Deltauv_dict = {}
e_dict = {}
pi_shares = {}  # π
phi_dict= {}

"数学工具部分"
def mod_inverse(a, p):  # 计算 a 在有限域 F_p 中的逆元素 (模逆元)
    return pow(a, p - 2, p)  # 使用费马小定理计算逆元 a^(p-2) % p

def hash_function_manyinput(*args):  # 计算哈希值，将输入转换为唯一的整数
    data = ''.join(map(str, args)).encode()  # 将输入参数转换为字符串并拼接，然后编码成字节
    return hash_function_data(data)

def hash_function_data(data):  # 计算哈希值
    return hashlib.sha256(data).digest()

def lagrange_interpolation_coeffs(x_values, y_values, p):  # 拉格朗日插值法，计算多项式系数
    nn = len(x_values)
    coeffs = [0] * nn  # 用来存储多项式系数的列表（从常数项到最高次项）
    # 对于每一个 x_i
    for i in range(nn):
        xi = x_values[i]
        yi = y_values[i]
        # L_i(x) = ∏_{j != i} (x - x_j) / (x_i - x_j)
        # 计算 L_i(x) 的系数
        li_coeffs = [1]  # 初始化 L_i(x) 为常数 1
        for j in range(nn):
            if i != j:
                # 构造多项式 (x - x_j) / (x_i - x_j)
                # 分子部分是 (x - x_j)
                # 分母部分是 (x_i - x_j) 的逆元
                x_j = x_values[j]
                denominator = (xi - x_j) % p
                denominator_inv = mod_inverse(denominator, p) % p
                # 现在 L_i(x) * (x - x_j) -> 乘以 (x - x_j)
                li_coeffs = multiply_polynomials(li_coeffs, [denominator_inv, -x_j * denominator_inv % p], p)
        # 计算最终的多项式 L_i(x) * y_i
        li_coeffs = [c * yi % p for c in li_coeffs]
        # 将 L_i(x) 加到最终的多项式系数中
        coeffs = add_polynomials(coeffs, li_coeffs, p)
    return coeffs

def multiply_polynomials(p1, p2, p):  # 计算两个多项式的乘积
    result = [0] * (len(p1) + len(p2) - 1)
    for i in range(len(p1)):
        for j in range(len(p2)):
            result[i + j] = (result[i + j] + p1[i] * p2[j]) % p
    return result

def add_polynomials(p1, p2, p):
    # 对应位置相加
    length = max(len(p1), len(p2))
    p1 = p1 + [0] * (length - len(p1))
    p2 = p2 + [0] * (length - len(p2))
    return [(p1[i] + p2[i]) % p for i in range(length)]

def generate_vandermonde_matrix(rows, cols, prime):
    """ 生成 Vandermonde 矩阵，使用模 p 运算 """
    base_values = list(range(1, cols + 1))  # 生成 Vandermonde 矩阵的基
    matrix = np.array([[pow(base_values[j], i, prime) for j in range(cols)] for i in range(rows)])
    return matrix

"多项式生成部分"
# 生成随机多项式 F(X)，其阶数为 d，且满足 F(0) = F(-1) = ... = F(-a+1) = s
def generate_polynomial_f(s):
    x = symbols('x')
    x_values = list(range(-a + 1, 1))  # x = [-a+1, -a+2, ..., 0]
    y_values = [s] * a  # 对应的 y 值都是 s
    # 随机生成 t 个额外的点
    for i in range(t):
        x_random = random.randint(1, p - 1)  # 随机生成 x 点，确保 x 不为 0 到 -a+1
        y_random = random.randint(1, p - 1)  # 随机生成对应的 y 点
        x_values.append(x_random)
        y_values.append(y_random)
    # 使用拉格朗日插值法计算多项式系数
    coeffs = lagrange_interpolation_coeffs(x_values, y_values, p)
    # poly = Poly(coeffs, x, domain=GF(p))
    poly = Poly(coeffs, x)  # 手动给模p,这就不限制在有限域上了
    return poly

# 生成一个随机多项式 H(x)
def generate_polynomial_h():
    x = symbols('x')
    # 生成多项式的随机系数
    coeffs = [random.randint(1, p - 1) for _ in range(d_prime + 1)]  # 阶数为 d_prime
    poly = Poly(coeffs, x)  # 创建一个随机系数的多项式
    return poly

def generate_polynomial_z(u):
    x = symbols('x')
    # 计算 x 值，即 Zu(1 - v) = e_{u,v}
    x_values = [1 - v for v in range(1, a + 1)]
    # 取对应的 y 值，即 e_{u,v}
    y_values = [e_dict[(u, v)] for v in range(1, a + 1)]
    # 使用拉格朗日插值法计算多项式系数
    coeffs = lagrange_interpolation_coeffs(x_values, y_values, p)
    # poly = Poly(coeffs, x, domain=GF(p))
    poly = Poly(coeffs, x)
    return poly

def generate_polynomial_y(x_values, y_values):
    x = symbols('x')
    # 使用拉格朗日插值法计算多项式系数
    coeffs = lagrange_interpolation_coeffs(x_values, y_values, p)
    # poly = Poly(coeffs, x, domain=GF(p))
    poly = Poly(coeffs, x)
    return poly


"schnorr签名、ElGamal 加密算法部分"
def schnorr_sign(message, priv_key):  # schnorr签名生成部分，用于验证全局公私钥生成的正确性
    # 1. 选择一个随机整数r
    r = util.randrange(SECP256k1.order)
    # 2. 计算r点 (rG)
    r_point = r * SECP256k1.generator
    # 3. 计算e = H(r || m) (m为消息，r是rG的x坐标)
    r_bytes = r_point.x().to_bytes(32, byteorder='big')
    message_bytes = message.encode('utf-8')
    e = string_to_number(hash_function_data(r_bytes + message_bytes))
    # 4. 计算签名s = r - e * priv_key
    s = (r - e * priv_key) % SECP256k1.order
    # 返回签名 (r, s)
    return r_point.x(), s

def schnorr_verify(message, signature, pub_key):  # schnorr签名验证部分
    r, s = signature
    # 1. 计算e = H(r || m)
    r_bytes = r.to_bytes(32, byteorder='big')
    message_bytes = message.encode('utf-8')
    e = string_to_number(hash_function_data(r_bytes + message_bytes))
    # 2. 计算r' = sG + e * pub_key
    r_prime = s * SECP256k1.generator + e * pub_key
    # 3. 验证 r' 的 x 坐标是否等于 r
    return r_prime.x() == r

# 加密函数是 ElGamal 加密
# 《现代密码学教程》P205
def elgamal_encrypt(public_key, plaintext):
    # 在椭圆曲线上选择一点
    P_t_private_key = random.randint(1, p - 1)  # 随机生成一个私钥
    P_t = P_t_private_key * G  # 通过私钥计算对应的公钥点P_t
    pt_x, pt_y = P_t.x(), P_t.y()
    # 选择一个随机数 k
    k = random.randint(1, p-1)
    # 计算 计算点P1=(x1,y1)=kG,传输的加密数据1
    C1 = k * G
    # 计算 Pt+k*对方公钥,传输的加密数据2
    C2 = P_t+k * public_key  # 加密时的第二项是 r 与公钥点乘
    # 计算m*x_t+y_t,传输的加密数据3
    C3 = (plaintext * pt_x + pt_y)
    return C1, C2, C3

# 解密函数
def elgamal_decrypt(private_key, C1, C2, C3):
    # 接收方用自己的私钥计算出P_t
    s_C1 = private_key * C1
    P_t = C2 + (-s_C1)
    # 计算明文
    decrypted_plaintext = (C3 - P_t.y())/P_t.x()
    decrypted_plaintext = decrypted_plaintext % p
    return decrypted_plaintext

def encrypt_all_shares(public_keys):
    # 为每个参与者的每个 H_i(j) 共享份额加密
    for i in range(1, n + 1):
        for j in range(1, n +1):
            # 获取参与方 P_j 的公钥
            # public_key_j = public_keys[j-1]  # P_j 的公钥
            # 获取 Hi(j) 的共享份额
            poly_h = all_polynomials_h[i-1]
            H_ij = poly_h.eval({symbols('x'): j})
            # 对共享份额 H_ij 进行加密
            C1, C2, C3 = elgamal_encrypt(public_keys[j-1], H_ij)
            # 将加密结果存储到 encrypted_shares 中
            encrypted_shares.append((i, j, C1, C2, C3))  # 存储参与者 i 和 j 的加密结果
def decrypt_all_shares(private_keys):
    for enc_share in encrypted_shares:
        i, j, C1, C2, C3 = enc_share
        # print(f"参与方 i={i} 对 j={j} 的加密结果：")
        # print(f"    C1: {C1}")
        # print(f"    C2: {C2}")
        # print(f"    C2: {C3}")
        # 获取参与方 P_j 的私钥
        private_key_j = private_keys[j - 1]  # 私钥数组索引从0开始
        # 使用私钥解密共享份额
        decrypted_share = elgamal_decrypt(private_key_j, C1, C2, C3)
        # 将解密结果存储到 decrypted_shares 中
        decrypted_shares.append((i, j, decrypted_share))

# 为所有参与者生成承诺
def generate_commitments():
    # 定义评估点 v
    evaluation_points = list(range(-a + 1, t + a))  # v ∈ [−a + 1, t + a − 1]
    # 遍历所有参与者
    for i in range(1, n + 1):
        # 获取第i个参与者的多项式
        poly_h = all_polynomials_h[i - 1]
        # 在每个评估点 v 处评估 H_i(x) 并计算承诺值
        commitment = []
        for v in evaluation_points:
            H_v = poly_h.eval({symbols('x'): v}) % p
            # 计算承诺 H_i(v) · G （H_v 是评估结果）
            commitment_value = H_v * G  # 点乘
            # commitment.append((v, H_v, commitment_value))  # 存储评估点、H(v) 和承诺值
            commitment.append((v, commitment_value))  # 存储评估点和承诺值
        # 将第i个参与者的承诺值添加到 commitments 列表中
        commitments.append(commitment)

# 一致性协议部分
def protocol_manage_sets_verify_and_complain(decrypted_shares, commitments):
    # 初始化集合
    QUAL = set()  # 合格集合
    BAD = set()  # 恶意集合
    HOLD = set()  # 持有集合
    # 集合参数
    d1 = n - t  # d1 = |QUAL| + |BAD| = n − t
    d0 = n - t  # d0 = |HOLD| = n − t

    # Step 1: 扩展 QUAL
    for dealer_index, dealer_commitment in enumerate(commitments, start=1):
        if len(QUAL) < d1:
            # 只要 dealer 承诺的格式正确，就加入 QUAL
            QUAL.add(dealer_index)  # Dealer 编号从 1 开始

    # Step 2: 遍历所有 Shareholder 进行验证
    # 使用字典存储每个股东的投诉，键为股东编号，值为投诉列表（可能为空）
    shareholder_complaints = defaultdict(list)
    complaints = []  # 存储所有的投诉
    # 遍历所有解密后的共享份额，进行验证
    for i, j, decrypted_share in decrypted_shares:  # decrypted_shares 是一个列表，存储每个 (i, j, decrypted_share)
        if i in QUAL:  # 只处理 QUAL 内的 dealer
            # 验证股东 Pj 解密的 share 是否有效
            if i != j: # 自己不验证自己
                verification_passed = verify_share(i, j, decrypted_share, commitments)
                if not verification_passed:
                    # 如果验证失败，就记录该投诉
                    shareholder_complaints[j].append((i, j, decrypted_share))

    # Step 3: 处理 BAD
    for shareholder, shareholder_complaint_list in shareholder_complaints.items():
        for complaint in shareholder_complaint_list:
            dealer_i, shareholder_j, decrypted_share = complaint
            # 将恶意 dealer 从 QUAL 中移除，并加入 BAD
            QUAL.discard(dealer_i)
            BAD.add(dealer_i)
            complaints.append(complaint)
            # print(f"Dealer {dealer_i} is marked as BAD due to complaint.")

    # Step 4: 确定HOLD集合
    for shareholder, shareholder_complaint_list in shareholder_complaints.items():
        if(len(HOLD) < d0):  # 将前 d0 个广播了有效投诉集合（或空集合）的股东加入 HOLD 集合
            if shareholder not in BAD:
             HOLD.add(shareholder)
    # 如果无投诉， HOLD 集合取前 d0个
    if len(complaints) == 0:
        for i in range(1, n + 1):  # 从 1 开始计算
            if i in QUAL:
                HOLD.add(i)

    return QUAL, BAD, HOLD

# 计算拉格朗日基函数 λk
def lagrange_coefficient(k, j, points):
    result = 1
    for m in points:
        if m != k:
            numerator = (j - m) % p
            denominator = (k - m) % p
            denominator_inv = mod_inverse(denominator, p)
            term = (numerator * denominator_inv) % p
            result = (result * term) % p
    return result

# 验证共享份额
def verify_share(i, j, decrypted_share, commitments):
    # 手动整个恶意节点
    if i == 2:
        return False
    if i == 4:
        return False
    # 获取当前 dealer 的承诺
    dealer_commitment = commitments[i - 1]  # Dealer 索引从 1 开始
    # 计算左侧值：解密后的 share 乘以 G
    left_side = decrypted_share * G
    # 计算右侧值：Lagrange 插值计算重建的多项式值
    points = list(range(-a + 1, t + a))
    right_side = 0 * G
    # 对每个点 k 进行加权求和
    for k in points:
        # 计算 λk，即 Lagrange 基函数的系数
        lambda_k = lagrange_coefficient(k, j, points)
        commitment_value = dealer_commitment[k+a-1][1]  # 提取承诺值部分
        right_side += lambda_k * commitment_value  # 加权求和，得到右侧
    # 进行验证：比较左侧和右侧的值是否相等
    return left_side.x() == right_side.x()

# 主函数
def main():
    print(f"参与方的人数 n: {n}")
    print("\033[31m{:-^50s}\033[0m".format(" 生成s、S、F(x)、σi、Si "))
    # 生成秘密密钥 s
    s = random.randint(1, p - 1)  # 随机生成秘密密钥 s，确保在模 p 内
    # 全局公钥 S = s * G
    S = s * G
    # 生成多项式 F(X)
    poly_f = generate_polynomial_f(s)
    # 打印生成的多项式和秘密密钥
    print(f"生成的秘密密钥 s: {s}")
    print(f"生成的全局公钥 S: {S}")
    print(f"生成的多项式 F(X): {poly_f}")
    # # 打印验证 F(0), F(-1), ..., F(-a+1) 是否等于 s
    # print("验证 F(0), F(-1), ..., F(-a+1) 是否为 s:")
    # for i in range(a):
    #     value = poly_f.eval(i - a + 1) % p  # F(i - a + 1)
    #     print(f"F({i - a + 1}) = {value}")

    # 计算每个参与方 Pi 持有的共享份额 σ_i = F(i)，i 从 1 开始
    for i in range(1, n + 1):  # 从 1 开始计算
        share = poly_f.eval(i) % p  # 计算 F(i)
        sigma_shares.append(share)
    # 打印每个参与方 Pi 持有的共享份额 σ_i = F(i)
    for i in range(n):
        print(f"参与方 P{i + 1} 持有的私钥份额 σ{i + 1} = F({i + 1}) = {sigma_shares[i]}")
    # 每个参与方的公钥份额 S_i = σ_i * G
    public_keys = [share * G for share in sigma_shares]
    # 打印每个参与方的公钥份额 Si
    for i in range(n):
        print(f"参与方 P{i + 1} 持有的公钥份额 S{i + 1} = {public_keys[i]}")

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 用s和S进行传统Schnorr签名及验证 "))
    # 签名生成
    message = "Hello, Schnorr!"
    print(f"消息message: {message}")
    signature = schnorr_sign(message, s)
    print(f"用长期秘密密钥s进行签名Signature: {signature}")
    # 签名验证
    is_valid = schnorr_verify(message, signature, S)
    print(f"用公钥进行验证Signature valid: {is_valid}")

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 生成Hi(x)及参与者的承诺值 "))
    # 生成每个参与者的 H(x) 多项式，并将其存储在 all_polynomials_h 列表中
    for i in range(1, n + 1):
        poly_h = generate_polynomial_h()
        # 将每个多项式保存在 all_polynomials 列表中
        all_polynomials_h.append(poly_h)
    print("所有参与者的 H(x):")  # 打印所有参与者的 H(x)
    for i in range(n):
        poly_h = all_polynomials_h[i]
        print(f"参与者 {i + 1} 的 H(x): {poly_h}")
    # 为所有参与者生成承诺值
    generate_commitments()
    # 打印所有参与者的承诺值
    print("所有参与者的承诺值：")
    for i, commitment in enumerate(commitments, start=1):
        print(f"参与者 {i} 的承诺值：")
        for v, commitment_value in commitment:
            print(f"    H{i}({v})承诺值: {commitment_value}")

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 对ρij = Hi(j)进行加密解密 "))
    #实现 Encrypt the share ρij = Hi(j)
    encrypt_all_shares(public_keys) # 进行加密广播，公钥加密
    # 打印所有加密后的共享份额
    # print("所有加密后的共享份额：")
    # for enc_share in encrypted_shares:
    #     i, j, C1, C2, C3 = enc_share
    #     print(f"参与方 P_{i} 对 P_{j} 的加密结果：")
    #     print(f"    C1: {C1}")
    #     print(f"    C2: {C2}")
    #     print(f"    C2: {C3}")
    # # 执行解密操作
    decrypt_all_shares(sigma_shares)  # 私钥解密
    # # 打印所有解密后的共享份额
    # print("所有解密后的共享份额：")
    # for dec_share in decrypted_shares:
    #     i, j, decrypted_share = dec_share
    #     poly_h = all_polynomials_h[i - 1]
    #     H_ij = poly_h.eval({symbols('x'): j})
    #     print(f"参与方 P_{i} 对 P_{j} 的解密结果：")
    #     print(f"    解密后的共享份额 : {decrypted_share}")
    #     print(f"    应与对应的Hij一致: {H_ij % p}")


    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 一致性协议部分，确定三个集合 "))
    # 初始化集合
    QUAL = set()  # 合格集合
    BAD = set()  # 恶意集合
    HOLD = set()  # 持有集合
    QUAL, BAD, HOLD = protocol_manage_sets_verify_and_complain(decrypted_shares, commitments)
    print(f"QUAL: {QUAL}")
    print(f"BAD: {BAD}")
    print(f"HOLD: {HOLD}")

    b= len(QUAL) - (t - len(BAD))
    QUAL_list = sorted(list(QUAL))  # 确保 QUAL 是有序的
    print(f"生成的b为：{b}")

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 生成超可逆矩阵Ψ "))
    # 生成超可逆矩阵
    # 生成 super-invertible Vandermonde 矩阵 Ψ (b x |QUAL|)
    psi_matrix = generate_vandermonde_matrix(b, len(QUAL_list), p)
    # print("生成的Vandermonde 矩阵 (Ψ):")
    # print(psi_matrix)

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 计算Hu(x), ru,v, Ru,v, ρju "))
    for u in range(b):
        # 计算 Hu(x) = sum(ψu_i * Hi(x))
        Hu = sum(psi_matrix[u, i] * all_polynomials_h[QUAL_list[i] - 1] for i in range(len(QUAL_list)))
        Hu_list.append(Hu)
        # print(f"\nHu(x) = H{u+1}(x): {Hu}")

        for v in range(1, a+1):
            ruv = Hu(1 - v) % p  # ru,v = Hu(1 - v)
            ru_dict[(u+1, v)] = ruv
            Ruv = ruv * G  # Ru,v = ru,v * G
            Ru_dict[(u + 1, v)] = Ruv
            # print(f"ru,v = r{u+1},{v} = {ruv}")
            # print(f"Ru,v = R{u+1},{v} = {Ruv}")

        for j in HOLD:
            # 计算 ρju = Hu(j) = sum(ψu_i * Hij)
            rhoju = sum(psi_matrix[u, i] * all_polynomials_h[QUAL_list[i] - 1].eval({symbols('x'): j}) for i in range(len(QUAL_list))) % p
            rhoju_dict[(j, u+1)] = rhoju
            # print(f"ρ_u,j = ρ_{u+1},{j} = {rhoju}")
            # print(f"H_u,j = H_{u+1},{j} = {Hu.eval(j) % p }")  # 这两行应该一样

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 进行Signature share generation部分 "))
    # 生成消息Muv,u ∈ [b], v ∈ [a]
    messages = {(u, v): f"Message_{u}_{v}".encode() for u in range(1, b + 1) for v in range(1, a + 1)} # (1, 1): b'Message_1_1'
    for u in range(1, b+1):
        for v in range(1, a+1):
            delta_uv = string_to_number(hash_function_manyinput(S, QUAL, Ru_dict[(u, v)], messages[(u, v)])) % p
            deltauv_dict[(u, v)] = delta_uv
            Delta_uv = delta_uv * G
            Deltauv_dict[(u, v)] = Delta_uv
            # print(f"deltau,v = delta{u},{v} = {delta_uv}")
            # print(f"Deltau,v = Delta{u},{v} = {Delta_uv}")

            e_uv = string_to_number(hash_function_manyinput(S, (Deltauv_dict[(u, v)] + Ru_dict[(u, v)]).x(), messages[(u, v)]))  # 为了保证一致性，采用x坐标，不然地址不一样
            e_dict[(u, v)] = e_uv
            # print(f"e_u,v = e_{u},{v} = {e_uv}")

        # 计算 Zu(x) 多项式，使得 Zu(1 - v) = e_u_v[v]
        Zu_poly = generate_polynomial_z(u)
        all_polynomials_z.append(Zu_poly)
        # print(f"生成的Zu_poly多项式Z{u}_poly: {Zu_poly}")

    # 签名份额生成
    # 计算 πu_j
    for j in HOLD:
        for u in range(1, b + 1):
            poly_z = all_polynomials_z[u - 1]
            zu_j = poly_z.eval({symbols('x'): j}) % p
            sigma_j = sigma_shares[j-1]
            rho_ju = rhoju_dict[(j, u)]
            pi_shares[(j, u)] = (zu_j * sigma_j + rho_ju) % p
            # print(f"j = {j} in HOLD, u= {u}, 生成的pai_ju = {pi_shares[(j, u)]}")

    # 签名重构
    # 收集d_prime+1个有效签名份额pi_shares[(j, u)],插值恢复多项式Y
    # 计算 Yu(x) 多项式，使得 Yu(j) = pi_shares[(j, u)]
    for u in range(1, b + 1):
        # 如果pi_shares[(j, u)]通过验证，收集d_prime+1个插值恢复多项式Y
        yu_poly_x_values = []
        yu_poly_y_values = []
        flag = 0
        for j in HOLD:
            #pi_shares[(j, u)]通过验证
            yu_poly_x_values.append(j)
            yu_poly_y_values.append(pi_shares[(j, u)])
            flag += flag
            if(flag == d_prime + 1):
                break

        Yu_poly = generate_polynomial_y(yu_poly_x_values, yu_poly_y_values)
        all_polynomials_y.append(Yu_poly)
        # print(f"生成的Yu_poly多项式Y{u}_poly: {Yu_poly}")

    # phiu, v = Yu(1 − v)
    for u in range(1, b + 1):
        for v in range(1, a + 1):
            phi_uv = all_polynomials_y[u-1].eval(1 - v) % SECP256k1_n
            phi_dict[(u, v)] = phi_uv
            # print(f"PHI_u,v = PHI{u},{v} = {phi_uv}")

    print("-" * 50)
    print("-" * 50)
    print("\033[31m{:-^50s}\033[0m".format(" 签名生成与验证 "))
    # 计算 Schnorr 签名
    schnorr_signatures = {}
    for u in range(1, b + 1):
        for v in range(1, a + 1):
            schnorr_signatures[(u, v)] = ((Deltauv_dict[(u, v)] + Ru_dict[(u, v)]), deltauv_dict[(u, v)] + phi_dict[(u, v)])

    # 输出签名
    print("Schnorr Signatures:")
    for (u, v), signature in schnorr_signatures.items():
        print(f"对于消息M_{u},{v} 生成的schnorr签名为 {signature}")

    # 接下来进行验证
    for (u, v), (qian, hou) in schnorr_signatures.items():
        # print(f"对于消息 M_{u},{v} : {messages[(u, v)]}")
        leftside = hou * G
        e = string_to_number(hash_function_manyinput(S, qian.x(), messages[(u, v)]))
        assert e == e_dict[(u,v)]
        rightside = qian + e * S
        # print(f"左侧值: {leftside}")
        # print(f"右侧值: {rightside}")
        if leftside.x() == rightside.x():
            if leftside.y() == rightside.y():
                print(f"对于消息M_{u},{v} 签名验证成功")
        else:
            print(f"对于消息M_{u},{v} 签名验证失败")

if __name__ == "__main__":
    main()
